package binary_tree.leetcode.medium;

/**
 * @author bruin_du
 * @description 最大的异或
 * @date 2022/8/20 22:12
 **/
public class OfferII067_FindMaximumXOR {
    class Node {
        Node[] next;

        public Node() {
            next = new Node[2];
        }
    }
    Node root;
    public int findMaximumXOR(int[] nums) {
        root = new Node();
        //题目中为两个非负数
        int max = 0;
        for (int num : nums) {
            insert(num);
            max = Math.max(max, num ^ find(num));
        }
        return max;
    }
    public void insert(int num) {
        Node cur = root;
        //为什么要从高位开始？
        //0011 ^ 1011 > 0011 ^ 0111，也就是说，从左往右要尽可能地找到与当前位值不同的数字，而且，越早不同，得到的结果越大；
        for (int i = 30; i >= 0; i--) {// 题目范围为非负数，高31位移动到低1位只要右移30位
            int a = (num >>> i) & 1;
            if (cur.next[a] == null) {
                cur.next[a] = new Node();
            }
            cur = cur.next[a];
        }
    }

    // 返回当前前缀树中与num做异或能够取得最大值的数字。取出后再在外部做异或运算。
    public int find(int num) {
        Node cur = root;
        int res = 0;
        for (int i = 30; i >= 0; i--) {
            // 与bit相反（指0-1相反）的节点若不存在，bit不变，若存在，取相反
            int a = (num >>> i) & 1, b = 1 - a;
            a = cur.next[b] == null ? a : b;
            res += (a << i);// 累计res
            cur = cur.next[a];
        }
        return res;
    }
}
